import Foundation

// MARK: 单链表 
public class SinglyLinkedList: NSObject {
    public var head: ListNode?
    public var tail: ListNode?
    
    public init(arr: [Int]) {
        super.init()

        for num in arr {
            appendToTail(num)
        }        
    }
    
    
    // 尾插法
    public func appendToTail(_ val: Int) {
        if tail == nil {
            tail = ListNode(val)
            head = tail
        } else {
            tail!.next = ListNode(val)
            tail = tail!.next
        }
    }
    
    // 头插法
    public func appendToHead(_ val: Int) {
        if head == nil {
            head = ListNode(val)
            tail = head
        } else {
            let temp = ListNode(val)
            temp.next = head
            head = temp
        }
    }
    
    public func node(at index: Int) -> ListNode? {
        var temp = head
        var j = 0
        while temp != nil && j < index {
            temp = temp!.next
            j += 1
        }
        guard temp != nil && j == index else {
            fatalError("越界了")
        }
        return temp
    }
    
    // 查找第i个元素数据
    public subscript(index: Int) -> Int {
        get {
            var temp = head
            var j = 0
            while temp != nil && j < index {
                temp = temp!.next
                j += 1
            }
            guard temp != nil && j == index else {
                fatalError("越界了")
            }
            return temp!.val
        }
        set(newValue) {
            var temp = head
            var j = 0
            while temp != nil && j < index-1 {
                temp = temp!.next
                j += 1
            }
            
            guard temp != nil && j == index-1 else {
                fatalError("越界了")
            }
            
            let node = ListNode(newValue)
            node.next = temp!.next
            temp!.next = node
        }
    }
    
    public func removeFirst() -> Int {
        guard let temp = head else {
            fatalError("越界了")
        }
        head = temp.next
        return temp.val
    }
    
    public func remove(at index: Int) -> Int {
        var temp = head
        var j = 0
        while temp != nil && j < index-1 {
            temp = temp!.next
            j += 1
        }
        guard temp != nil && j == index-1 else {
            fatalError("越界了")
        }
        
        guard temp!.next != nil else {
            fatalError("越界了")
        }
        
        let result = temp!.next
        temp!.next = result!.next
        
        return result!.val
    }
    
    public func removeAll() {
        head = nil
        tail = nil
    }
    
    public override var description: String {
        var temp = head
        var desc = "{"
        while temp != nil {
            desc += "\(temp!.val)"
            temp = temp!.next
            if temp != nil {
                desc += " -> "
            }
        }
        desc += "}"
        return desc
    }
}

public func linkNodeString(_ head: ListNode?) -> String {
    var temp = head
    var desc = "{"
    while temp != nil {
        desc += "\(temp!.val)"
        temp = temp!.next
        if temp != nil {
            desc += " -> "
        }
    }
    desc += "}"
    return desc
}
